// https://www.lintcode.com/problem/386/

class Solution {
public:
    /**
     * @param s: A string
     * @param k: An integer
     * @return: An integer
     */
    int lengthOfLongestSubstringKDistinct(string &s, int k) {
        map<char, int> rec;
        int max_len = 0;
        int l = 0;
        int r = 0;
        if (s.length() < k) {
            return s.length();
        }
        while (r < s.length()) {
            rec[s[r]]++;
            if (rec[s[r]] == 1) {
                k--;
            }
            // if (k == 0) {
            while (k < 0) {
                // max_len = max(max_len, r - l + 1);
                rec[s[l]]--;
                if (rec[s[l]] == 0) {
                    k++;
                }
                l++;
            }
            max_len = max(max_len, r - l + 1);
            r++;
        }
        return max_len;
    }
};